package org.algorithm.biubiu.wheel_1.回溯算法;

import java.util.ArrayList;
import java.util.List;

/**
 * 找出所有相加之和为n 的k个数的组合，且满足下列条件：
 * <p>
 * 只使用数字1到9
 * 每个数字最多使用一次
 * 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
 * 216. 组合总和 III
 * 链接：https://leetcode-cn.com/problems/combination-sum-iii
 */
public class $4月25日$组合总和3 {


    List<List<Integer>> res = new ArrayList();
    int target ;
    int count;
    public List<List<Integer>> combinationSum3(int k, int n) {
        this.count = k;
        this.target= n;
        backTrack(1,0);
        return  res;
    }



    List<Integer> cur = new ArrayList();
    public void backTrack(int step,int curSum){
        if(cur.size() == count &&curSum == target){
            res.add(new ArrayList(cur));
            return;
        }


        for(int i =step;i<10;i++){
            cur.add(i);
            curSum +=i;
            backTrack(i+1,curSum);
            curSum -=i;
            cur.remove(cur.size()-1);
        }

    }
}
